package paravyan;

public class BinarySearchTree<T extends Comparable<T>> implements Comparable<T> {

	private T data;
	private BinarySearchTree<T> left;
	private BinarySearchTree<T> right;
	private BinarySearchTree<T> parent;

	public Object getData() {
		return data;
	}

	public void setData(T data) {
		this.data = data;
	}

	public BinarySearchTree<T> getLeft() {
		return left;
	}

	public void setLeft(BinarySearchTree<T> left) {
		this.left = left;
	}

	public BinarySearchTree<T> getRight() {
		return right;
	}

	public void setRight(BinarySearchTree<T> right) {
		this.right = right;
	}

	public BinarySearchTree() {
		this(null);
	}

	public BinarySearchTree(T obj) {
		this.data = obj;
		this.left = null;
		this.right = null;
		this.parent = null;
	}

	public void insert(T obj) throws Exception {
		if (obj == null)
			throw new Exception("Cannot add null object");
		if (this.data == null) {
			this.data = obj;
			return;
		}
		if (obj.compareTo(this.data) < 0) {
			if (this.left != null) {
				this.left.insert(obj);
			} else {
				this.left = new BinarySearchTree<T>(obj);
				this.left.parent = this;
			}
		} else {
			if (obj.compareTo(this.data) > 0) {
				if (this.right != null) {
					this.right.insert(obj);
				} else {
					this.right = new BinarySearchTree<T>(obj);
					this.right.parent = this;
				}
			}
		}
	}

	public void remove(T obj){

		if (this == null)
			throw new NullPointerException("Cannot remove object " + obj
					+ "from the tree!");

		if (obj.compareTo(this.data) > 0) {
			this.right.remove(obj);
		} else {
			if (obj.compareTo(this.data) < 0) {
				this.left.remove(obj);
			} else {
				if (left == null && right == null) {
					if (find(obj) == parent.left)
						parent.left = null;
					else
						parent.right = null;
					return;
				}
				if ((left != null && right == null)
						|| (left == null && right != null)) {
					if (left != null && right == null) {
						parent.left = null;
						left.parent = parent;
						parent.left = left;
						return;
					}
					if (left == null && right != null) {
						parent.right = null;
						right.parent = parent;
						parent.right = right;
						return;
					}
				}
				BinarySearchTree<T> min = right.minimum();
				if (min != null) {
					this.data = min.data;
					right.remove(min.data);
				}

			}
		}
	}

	public BinarySearchTree<T> find(T obj) {
		if (this.data.equals(obj))
			return this;
		if (obj.compareTo(this.data) < 0 && this.left != null)
			return this.left.find(obj);

		if (obj.compareTo(this.data) > 0 && this.right != null)
			return this.right.find(obj);
		return null;

	}

	// left->data->right
	public String infixTraverse() {
		if (this == null)
			throw new NullPointerException("Tree is empty");
		String res = "";
		if (this.left != null) {
			res += this.left.infixTraverse();
		}
		res += this.data.toString() + " ";
		if (this.right != null) {
			res += this.right.infixTraverse();
		}
		return res;
	}

	// data->left->right
	public String prefixTraverse() {
		if (this == null)
			throw new NullPointerException("Tree is empty");
		String res = "";
		res += this.data.toString() + " ";
		if (this.left != null) {
			res += this.left.prefixTraverse();
		}
		if (this.right != null) {
			res += this.right.prefixTraverse();
		}
		return res;
	}

	public boolean exists(T obj) {
		if (this.data.equals(obj))
			return true;
		try {
			return (obj.compareTo(this.data) < 0) ? left.exists(obj) : right
					.exists(obj);
		} catch (NullPointerException e) {
			return false;
		}
	}

	private BinarySearchTree<T> minimum() {
		if (this == null)
			return null;
		BinarySearchTree<T> tmp = this;
		while (tmp.left != null)
			tmp = tmp.left;
		return tmp;
	}

	public int compareTo(T obj) {
		return this.data.compareTo(obj);
	}

}
